package com.chj.zhongji.class14;

//https://tangshusen.me/2019/11/03/Buy-and-Sell-Stock/
public class Code02_BestTimetoBuyandSellStock2 {
	public static int maxProfit(int[] prices) {
		if (prices == null || prices.length == 0) {
			return 0;
		}
		int ans = 0;
		int min = prices[0];
		int max = prices[0];
		for (int i = 1; i < prices.length; i++) {
			if (prices[i] >= prices[i - 1]) {
				max = prices[i];
			} else {
				ans += max - min;
				min = prices[i];
				max = prices[i];
			}
		}
		return ans + max - min;
	}

//	https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/tan-xin-suan-fa-by-liweiwei1419-2/
	public static int maxProfitDp(int[] prices) {
		int len = prices.length;
		if (len < 2) {
			return 0;
		}

		// 0：持有现金
		// 1：持有股票
		// 状态转移：0 → 1 → 0 → 1 → 0 → 1 → 0
		int[][] dp = new int[len][2];

		dp[0][0] = 0;
		dp[0][1] = -prices[0];

		for (int i = 1; i < len; i++) {
			// 这两行调换顺序也是可以的
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
		}
		return dp[len - 1][0];
	}

	public static void main(String[] args) {
		{
			int[] arr = { 7, 1, 5, 3, 6, 4 };
			System.out.println(maxProfit(arr));
			System.out.println(maxProfitDp(arr));
//			System.out.println(maxProfitDp2(arr));
		}

		{
			int[] arr = { 1, 2, 3, 4, 5 };
			System.out.println(maxProfit(arr));
			System.out.println(maxProfitDp(arr));
//			System.out.println(maxProfitDp2(arr));
		}

		{
			int[] arr = { 7, 6, 4, 3, 1 };
			System.out.println(maxProfit(arr));
			System.out.println(maxProfitDp(arr));
//			System.out.println(maxProfitDp2(arr));
		}
	}
}
